package org.lql.algo.codecrush.week004;

import java.util.LinkedList;

/**
 * @author: liangqinglong
 * @date: 2025-08-01 17:51
 * @description: 面试题 03.06. 动物收容所 <a href="https://leetcode.cn/problems/animal-shelter-lcci/description/">...</a>
 **/
public class AnimalShelf {

	/**
	 * 动物收容所。有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。
	 * 在收养该收容所的动物时，收养人只能收养所有动物中“最老”（由其进入收容所的时间长短而定）的动物，
	 * 或者可以挑选猫或狗（同时必须收养此类动物中“最老”的）。换言之，收养人不能自由挑选想收养的对象。
	 * 请创建适用于这个系统的数据结构，实现各种操作方法，比如enqueue、dequeueAny、dequeueDog和dequeueCat。允许使用Java内置的LinkedList数据结构。
	 * <p>
	 * enqueue方法有一个animal参数，animal[0]代表动物编号，animal[1]代表动物种类，其中 0 代表猫，1 代表狗。
	 * <p>
	 * dequeue*方法返回一个列表[动物编号, 动物种类]，若没有可以收养的动物，则返回[-1,-1]。
	 */

	private int timestamp = 0; // 时间戳，用于标记进入顺序
	private LinkedList<int[]> dogs;
	private LinkedList<int[]> cats;


	public AnimalShelf() {
		dogs = new LinkedList<>();
		cats = new LinkedList<>();
	}

	public void enqueue(int[] animal) {
		// animal[0]：动物编号；animal[1]：种类（0=猫，1=狗）
		int[] entry = new int[]{animal[0], animal[1], timestamp++};
		if (animal[1] == 1) {
			dogs.addLast(entry);
		} else {
			cats.addLast(entry);
		}
	}

	public int[] dequeueAny() {
		if (dogs.isEmpty() && cats.isEmpty()) {
			return new int[]{-1, -1};
		} else if (dogs.isEmpty()) {
			return dequeueCat();
		} else if (cats.isEmpty()) {
			return dequeueDog();
		} else {
			// 比较两边队首谁更早加入
			if (dogs.peekFirst()[2] < cats.peekFirst()[2]) {
				return dequeueDog();
			} else {
				return dequeueCat();
			}
		}
	}

	public int[] dequeueDog() {
		if (dogs.isEmpty()) {
			return new int[]{-1, -1};
		}
		int[] dog = dogs.removeFirst();
		return new int[]{dog[0], dog[1]};
	}

	public int[] dequeueCat() {
		if (cats.isEmpty()) {
			return new int[]{-1, -1};
		}
		int[] cat = cats.removeFirst();
		return new int[]{cat[0], cat[1]};
	}
}
